"""
Problem 77: https://projecteuler.net/problem=77

It is possible to write ten as the sum of primes in exactly five different ways:

7 + 3
5 + 5
5 + 3 + 2
3 + 3 + 2 + 2
2 + 2 + 2 + 2 + 2

What is the first value which can be written as the sum of primes in over
five thousand different ways?
"""


# _*_ conding:UTF-8 _*_
'''
@author = Kuperain
@email = kuperain@aliyun.com
@IDE = VSCODE Python3.8.3
@creat_time = 2022/5/31
'''


from commonfuncs import primefunctools as pf
primesT = pf.primesTable(3)
primes = [n for n in range(1000) if primesT[n]]
# print(primes)

CH = dict()  # {(num,startPrimeIndex):count}


def decomposeTotal(num: int, startPrimeIndex: int):
    '''
    similarly with Problem 76:

    solutions can divide into 2 cases: with 2, without 2
        (1) with 2, have F(n-2) ways, where digit in [2,3,5,7,11...]
        (2) without 2, hav F'(n) ways, where digit in [3,5,7,11,...]
    F(n) = F(n-2) + F'(n)
    --> if n is even, F(n) = F(0) + F'(2) + F'(4) + F'(6) + F'(8) + ... + F'(n)
        if n is odd,  F(n) = F(1) + F'(3) + F'(5) + F'(7) + F'(9) + ... + F'(n)
        in other word, F'(n-k) means with 2*k, other digit in [3,5,7,11,...]

    >>> print(decomposeTotal(10,0))
    5
    >>> print(decomposeTotal(4,0))
    1
    '''

    if (num, startPrimeIndex) in CH:
        return CH[(num, startPrimeIndex)]

    if num == 0:
        CH[(num, startPrimeIndex)] = 1
        return 1

    minP = primes[startPrimeIndex]
    k = num/minP

    if k < 1:
        CH[(num, startPrimeIndex)] = 0
        return 0

    if k == 1:
        CH[(num, startPrimeIndex)] = 1
        return 1

    k = int(k)
    res = 0
    for i in range(k+1):
        CH[(num-i*minP, startPrimeIndex + 1)
           ] = decomposeTotal(num-i*minP, startPrimeIndex + 1)
        # print(
            # f'decomposeTotal({num-i*minP}, {startPrimeIndex + 1}) = {CH[(num-i*minP, startPrimeIndex + 1)]}')
        res += CH[(num-i*minP, startPrimeIndex + 1)]

    CH[(num, startPrimeIndex)] = res
    return res


def solution(limit: int = 5000) -> int:
    num = 2
    while True:
        if decomposeTotal(num, 0) > limit:
            return num
        else:
            num += 1


if __name__ == "__main__":
    import doctest
    doctest.testmod(verbose=False)

    print(solution())
    # 71
    # print(CH)
